package com.example;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #77. 组合
 * @Date 2022/2/23
 */
public class Combinations {

    private static List<List<Integer>> lists = new ArrayList<>();

    /**
     * 方法描述:给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * 你可以按 任何顺序 返回答案。
     *
     * 示例 1：
     * 输入：n = 4, k = 2
     * 输出：
     * [
     *   [2,4],
     *   [3,4],
     *   [2,3],
     *   [1,2],
     *   [1,3],
     *   [1,4],
     * ]
     * @param: [n, k]
     * @return: java.util.List<java.util.List<java.lang.Integer>>
     * @author: loubobooo
     * @date: 2022/2/25
     */
    public static List<List<Integer>> combine(int n, int k) {
        List<Integer> list = new ArrayList<>();
        backTracking(0, n, k, list);
        return lists;
    }


    private static void backTracking(int startIndex, int n, int k, List<Integer> list) {
        // 终止条件list数组大小等于k
        if (list.size() == k) {
            lists.add(new ArrayList<>(list));
            return;
        }
        // 遍历
        for (int i = startIndex; i <= n - (k - list.size()) + 1; i++) {// 优化的地方
            // 添加节点
            list.add(i);
            backTracking(i + 1, n, k, list);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {
        combine(4, 2);
    }

}
